package leetcode.f1t100;

import leetcode.struct.ListNode;

/**
 * 反转链表
 * https://leetcode.com/problems/reverse-nodes-in-k-group/
 *
 * @author lichx
 * @date 2021/12/8 15:16
 */
public class Q25_ReverseLinkedList {

    public static void main(String[] args) {
//        ListNode head = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,
//                new ListNode(5,new ListNode(6, new ListNode(7,
//                        new ListNode(8, new ListNode(9,new ListNode(10))))))))));
        ListNode head = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,
                new ListNode(5,null)))));
        ListNode newHead = new Q25_ReverseLinkedList().reverseKGroup(head, 2);
        while (newHead != null) {
            System.out.println(newHead.val);
            newHead = newHead.next;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1){
            return head;
        }
        ListNode virtualHead = new ListNode(0,head);
        ListNode cur = virtualHead;
        while(cur != null) {
            ListNode pre = cur;
            ListNode start = cur.next;
            for (int i = 1; i <= k; i++) {
                cur = cur.next;
                if(cur == null) {
                    return virtualHead.next;
                }
            }
            ListNode end = cur;
            cur = start;
            reverseK(pre, start, end, k);
            pre = cur;
        }
        return virtualHead.next;
    }

    public static void reverseK(ListNode head, ListNode start, ListNode end, int k) {
        ListNode cur = start;
        ListNode pre = end.next;
        ListNode next = cur.next;
        while(pre != end) {
            cur.next = pre;
            pre = cur;
            cur = next;
            next = cur == null ? null : cur.next;
        }
        head.next = end;
    }
}
